Добро пожаловать на урок 3 Концепции искусственного интеллекта (PolyU COMP5511). В этой сессии мы переходим от поиска пути одного агента к Состязательный поиск, где агенты действуют в конкурентных многоагентных средах. Мы также вводим Задачи удовлетворения ограничений (CSP), парадигму, где целью является найти состояние, удовлетворяющее определенному набору ограничений, а не путь.

Основные концепции

• Состязательный поиск: Фокусируется на алгоритмах, таких как Минимакс и Отсечение альфа-бета, чтобы принимать рациональные решения против интеллектуального противника.
• Дерево поиска Монте-Карло (MCTS): Исследует вероятностное принятие решений, служа основой для современных игровых ИИ, таких как AlphaGo.
• Удовлетворение ограничений: Моделирует задачи, используя Переменные, Домены и Ограничения, решая их с помощью Обратный поиск и Локальный поиск.

Анализ сложности

В состязательных условиях сложность пространства поиска часто определяется фактором ветвления игры $b$ и глубиной $d$, что приводит к вычислительной стоимости: $$O{b}^d$$ Этот экспоненциальный рост требует эффективных стратегий отсечения, таких как отсечение альфа-бета.